package com.hch.algorithm.leet;

import ch.qos.logback.classic.db.DBAppender;
import org.springframework.stereotype.Component;

import java.util.Arrays;

@Component
public class DynamicLeetBookImpl implements DynamicLeetBook {
    @Override
    public int fib(int n) {
        // 备忘录全初始化为 0
        int[] dp = new int[n + 1];
//        base case
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
        // 进行带备忘录的递归
//        return helper(memo, n);
    }

//    int[] memo;

    @Override
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
//        吧各个数组初始化为amount+1，需要最多的数量不会超过amount+1;
        Arrays.fill(dp, amount + 1);
//        base case
        dp[0] = 0;
        // 外层 for 循环在遍历所有状态的所有取值
        for (int i = 0; i < dp.length; i++) {
            // 内层 for 循环在求所有选择的最小值
            for (int coin : coins) {
//                子问题无解跳过
                if (i < coin) {
                    continue;
                }
//                上个状态的值加一就是当前最小的值
                int min = dp[i - coin] + 1;
                dp[i] = Math.min(dp[i], min);
            }

        }
        return dp[amount] == amount + 1 ? -1 : dp[amount];

////        备忘录
//        memo = new int[amount + 1];
//        Arrays.fill(memo, -666);
//        return coin(coins, amount);
    }

//    private int coin(int[] coins, int amount) {
//        //        确定 base case，
//        if (amount == 0) {
//            return 0;
//        }
//        if (amount < 0) {
//            return -1;
//        }
//        if (memo[amount] != -666) {
//            return memo[amount];
//        }
//        int res = Integer.MAX_VALUE;
////        遍历所有币值
//        for (int coin : coins) {
//            //        递归穷举所有情况
//            int subProblem = coin(coins, amount - coin);
//            if (subProblem == -1) {
//                continue;
//            }
////子问题加上当前币值的一枚硬币就是当前问题的解
//            int current = subProblem + 1;
////            取出当前问题的最优解
//            res = Math.min(res, current);
//
//
//        }
//        memo[amount] = res == Integer.MAX_VALUE ? -1 : res;
//        return memo[amount];
//    }

    private int helper(int[] memo, int n) {
        // base case
        if (n == 0 || n == 1) {
            return n;
        }
        // 已经计算过，不用再计算了
        if (memo[n] != 0) {
            return memo[n];
        }
        memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
        return memo[n];
    }
}
